package algorithms.roughgarden.part2.dynamicprogramming.allpair;

import static algorithms.common.CommonIOUtil.*;

public class Graph {
	private int[][] memoArray;
	private Vertex[] vertices;
	private int noOfVertices;
	
	private int[] shortestDistanceArray;
	private boolean isShortestDistanceCalculatedAtLeaseOnce = false;
	
	public Graph(int noOfVertices, int noOfEdges){
		vertices = new Vertex[noOfVertices];
		this.noOfVertices = noOfVertices;
		for(int i=0;i<noOfVertices;i++){
			vertices[i] = new Vertex(i+1);
		}

		memoArray = new int[noOfVertices+1][noOfVertices];
		resetGraph();
	}
	
	public void resetGraph(){
		for(int i=0;i<noOfVertices;i++){
			memoArray[0][i] = Integer.MAX_VALUE;
		}
	}
	
	public void addEdge(int sourceVertexNumber, int destinationVertexNumber, int weight){
		new Edge(getVertex(sourceVertexNumber), getVertex(destinationVertexNumber), weight);
	}
	
	private Vertex getVertex(int vertexNumber){
		return vertices[vertexNumber-1];
	}
	private int getMemoEntryByVertexNoAndMaxPathLenght(int vertexNumber, int maxPathLength){
		return memoArray[maxPathLength][vertexNumber-1];
	}
	
	private void setMemoEntryByVertexAndMaxPathLenght(int vertexNumber, int maxPathLength, int shortestPathLenght){
		memoArray[maxPathLength][vertexNumber-1] = shortestPathLenght;
	}
	/**
	 * Uses Bellman Ford algorithm to calculate array of shortest paths from source vertex to all other vertices
	 * @param sourceVertex from which all minimum distance to all other vertices needs to be calculated
	 * @return array containing shortest distance from sourceVertex to all other vertices.
	 */
	public int[] getShortestDistanceFromSource(int sourceVertex){
		/*if(shortestDistanceArray!=null)
			return shortestDistanceArray;*/
		memoArray[0][sourceVertex-1] = 0;
		for(int i=1;i<noOfVertices;i++){
			for(int vertexNumber = 1; vertexNumber <= noOfVertices ; vertexNumber++){
				setMemoEntryByVertexAndMaxPathLenght(vertexNumber, i, getMinimumPathforMaxPathlenght(i, getVertex(vertexNumber)));
			}
		}
		isShortestDistanceCalculatedAtLeaseOnce = true;
		return shortestDistanceArray = memoArray[noOfVertices-1];
	}
	/**
	 * Detects if negative cycles are present. This will run the Bellman Ford Algorithm if and only if it is not already run on
	 * this graph instance. Ideally this method should be called only once for any graph instance if for eg you're trying to find
	 * all pair shortest path, in which case cycle can be detected during first run and subsequent runs can be abandoned.
	 * @return true if graph contains a negative weight cycle, false otherwise
	 * @see #getShortestDistanceFromSource(int)
	 */
	public boolean hasNegativeCycles(){
		if(!isShortestDistanceCalculatedAtLeaseOnce){
			throw new RuntimeException("Calculate shortest distance at least once before calling this method");
		}
		for(int vertexNumber = 1; vertexNumber <= noOfVertices ; vertexNumber++){
			setMemoEntryByVertexAndMaxPathLenght(vertexNumber, noOfVertices, getMinimumPathforMaxPathlenght(noOfVertices, getVertex(vertexNumber)));
		}
		//Any change in optimal solution for more than n vertices denote presence of a negative cycle which can provide endless optimization
		return !isArrayContainEqualEntries(memoArray[noOfVertices-1], memoArray[noOfVertices]);
	}
	private int getMinimumPathforMaxPathlenght(int maxPathLength, Vertex vertex){
		long minPathLength = Integer.MAX_VALUE;
		long temp;
		for(Edge edge:vertex.getIncomingEdges()){
			temp = edge.getEdgeWeight()+(long)getMemoEntryByVertexNoAndMaxPathLenght(edge.getSourceVertex().getVertexNumber(), maxPathLength-1);
			if(temp < minPathLength){
				minPathLength = temp;
			}
		}
		int previousMin = getMemoEntryByVertexNoAndMaxPathLenght(vertex.getVertexNumber(), maxPathLength-1);
		if(previousMin < minPathLength){
			minPathLength = previousMin;
		}
		
		return (int)minPathLength;
	}
}
